package leetcode.code0808;

import java.util.HashMap;
import java.util.Map;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution implements IDebug {

	public double soupServings(int n) {
		if (n > 10000) {
			return 1;
		}
		Map<Integer, Map<Integer, Double>> map = new HashMap<>();
		return f(n, n, map);
	}

	private double f(int a, int b, Map<Integer, Map<Integer, Double>> map) {
		if (a <= 0) {
			return b <= 0 ? 0.5 : 1;
		}
		if (b <= 0) {
			return 0;
		}
		if (map.containsKey(a) && map.get(a).containsKey(b)) {
			return map.get(a).get(b);
		}
		double cur = 0d;
		cur += this.f(a - 100, b, map);
		cur += this.f(a - 75, b - 25, map);
		cur += this.f(a - 50, b - 50, map);
		cur += this.f(a - 25, b - 75, map);
		cur *= 0.25;
		map.computeIfAbsent(a, key -> new HashMap<>()).put(b, cur);
		return cur;
	}

	@Override
	public void debug4() {
		H.compare(1, this.soupServings(10145147));
//		H.compare(0.62500, this.soupServings(50));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
		
	}

}
